package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0338 
* @author      : ganwei 
* @date        : 2020年5月23日 
* @Description : 338. 比特位计数 
*/
public class Leetcode0338 {
    public int[] countBits(int num) {
    	if(num == 0) {
    		return new int[0];
    	}
    	
    	int[] dp = new int[num+1];
    	dp[0] = 0;
    	for(int i = 1; i <= num; i++) {
    		if(i % 2 == 0) {
    			dp[i] = dp[i/2];
    		}else {
    			dp[i] = dp[i-1] + 1;
    		}
    	}
    	
    	return dp;
    }
    
    public static void main(String[] args) {
    	
    }
}
